#include "fill.h"
#include <graphics.h>

#include <unordered_map>
#include <list>
#include <algorithm>
#include <iterator>
#include <stack>

using std::list;
using std::stack;
using std::unordered_map;
using std::vector;

#undef max
#undef min

struct Edge
{
	int ymax;
	double x;
	double dx;
	Edge(const int &_ymax, const double &_x, const double &_dx) : ymax(_ymax), x(_x), dx(_dx){};
};

void scanlinefill(const vector<Point> &polygon, int Color)
{
	/*
	预处理所需信息
	*/
	const size_t &len = polygon.size();
	vector<int> ymaxOFline(len);	  // 每条线的 ymax
	vector<double> dxdyOFline(len);	  // 每条线的 dx/dy
	vector<bool> is_scan(len, false); // 每条线是否已被扫描
	vector<int> s_index(len);		  // 对每个点的y从小到大排序的索引

	for (size_t i = 0, j; i < len; ++i)
	{
		j = (i + 1) % polygon.size();
		ymaxOFline[i] = std::max(polygon[i].y, polygon[j].y);
		if (polygon[i].y != polygon[j].y)
			dxdyOFline[i] = 1.0 * (polygon[i].x - polygon[j].x) / (polygon[i].y - polygon[j].y);
		else
			is_scan[i] = true;
		s_index[i] = i;
	}

	std::sort(s_index.begin(), s_index.end(), [&polygon](const int &i, const int j)
			  { return polygon[i].y < polygon[j].y; });

	const int &ymin = polygon[s_index.front()].y, &ymax = polygon[s_index.back()].y;

	/*
	初始化新边表
	*/
	unordered_map<int, list<Edge>> NET;

	for (const int &cur : s_index)
	{
		for (int i : {(cur + (int)len - 1) % (int)len, cur})
		{
			if (is_scan[i])
				continue;
			is_scan[i] = true;
			NET[polygon[cur].y].emplace_front(ymaxOFline[i], 1.0 * polygon[cur].x, dxdyOFline[i]);
		}
	}

	/*
	构造活性边表，画线
	*/
	list<Edge> AET;
	for (int y = ymin; y < ymax; ++y)
	{
		// NET[y] 插入 AET
		if (NET.find(y) != NET.end())
		{
			std::move(NET[y].begin(), NET[y].end(), std::back_inserter(AET));
		}

		// 按 x 从小到大排序(选择排序)，并匹配画线
		int i = 0;
		double pix_x[2] = {}, pix_ymax[2] = {};
		for (auto it = AET.begin(); it != AET.end(); ++it)
		{
			std::swap(*it, *std::min_element(it, AET.end(), [](const Edge &a, const Edge &b)
											 { return a.x < b.x; }));
			pix_ymax[i] = it->ymax;
			pix_x[i++] = it->x;
			if (i == 2)
			{
				i = 0;

				if (pix_x[0] > pix_x[1])
					std::swap(pix_x[0], pix_x[1]);
				else if (pix_x[0] == pix_x[1] && y < std::min(pix_ymax[0], pix_ymax[1]))
					putpixel(pix_x[0], y, Color);

				for (int x = pix_x[0]; x < pix_x[1]; ++x)
				{
					putpixel(x, y, Color);
				}
			}
		}

		// 更新 AET
		for (auto it = AET.begin(); it != AET.end();)
		{
			if (y + 1 == it->ymax)
			{
				it = AET.erase(it);
			}
			else
			{
				it->x += it->dx;
				++it;
			}
		}
	}
}
void myfloodfill(const Point &pos, COLORREF fillcolor, COLORREF boundary)
{
	// 初始化栈
	std::stack<Point> que;
	COLORREF cur = getpixel(pos.x, pos.y);
	if (cur == boundary || cur == fillcolor)
		return;
	// 初始点入栈
	que.push(pos);

	int width = getwidth(), height = getheight();
	while (!que.empty())
	{
		// 栈顶元素出栈
		Point t = que.top();
		que.pop();
		if (t.x < 0 || t.x >= width || t.y < 0 || t.y >= height)
			continue;

		cur = getpixel(t.x, t.y);
		if (cur == boundary || cur == fillcolor)
			continue;

		// 绘点
		putpixel(t.x, t.y, fillcolor);

		// 按四个方向遍历点
		const static int dx[4] = {0, 1, 0, -1},
						 dy[4] = {1, 0, -1, 0};
		for (int i = 0; i < 4; ++i)
		{
			int x = t.x + dx[i], y = t.y + dy[i];

			// 不在边界，且未被填充，入栈
			if (x < 0 || x >= width || y < 0 || y >= height)
				continue;

			cur = getpixel(x, y);
			if (cur == boundary || cur == fillcolor)
				continue;

			que.emplace(x, y);
		}
	}
}